//031. 货币面值的组合问题
//        在英国，货币是由英镑 ￡，便士 p 构成的。一共有八种钱币在流通：
//        1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) 和 ￡2 (200p).
//        要构造 ￡2 可以用如下方法：
//        1×￡1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
//        允许使用任意数目的钱币，一共有多少种构造 ￡2 的方法？
//        答案：73682


//居然第一反应没看出来是完全背包的变式
public class Week031 {
    static final int[] nums = {1, 2, 5, 10, 20, 50, 100, 200};//所有的钱币数额
    static final int N = 200;//所要构成的钱币数额
    static int ans = 0;

    static void dfs(int now, int n) {//now代表当前差的数目, n代表当前需要加入的是几号钱币
        if (n == 0) {//最后所剩的钱币一定可以由now个1构成, 且此时不能再分解了
            ++ans;
            return;
        }
        for (int i = now / nums[n]; i >= 0; --i) {//i枚举n号钱币的数量
            dfs(now - i * nums[n], n - 1);
        }
    }

    static void run() {
        //循环手都给你写断咯
        //for (int i = n / nums[len - 1]; i >= 0; --i) {
        //  for (int j = (n - (i * nums[len - 1])) / nums[len - 2]; j >= 0; --j) {
        //      for(int k=)
        //  }
        //}
        dfs(N, nums.length - 1);
        System.out.println(ans);
    }

    //二维完全背包
//    static void run() {
//        int nums[] = {0, 1, 2, 5, 10, 20, 50, 100, 200};
//        final int N = 200;
//        //dp[i][j]代表前i个货币面值能构成j便士的种类数
//        int[][] dp = new int[nums.length + 1][N + 1];
//        dp[0][0] = 1;
//        for (int i = 1; i < nums.length; ++i) {
//            for (int j = 0; j <= N; ++j) {
//                dp[i][j] = dp[i - 1][j];
//                if (j >= nums[i]) {
//                    dp[i][j] += dp[i][j - nums[i]];
//                }
//            }
//        }
//        System.out.println(dp[nums.length - 1][N]);
//    }

    //一维完全背包
//    static void run() {
//        int nums[] = {1, 2, 5, 10, 20, 50, 100, 200};
//        final int N = 200;
//        //dp[i]代表能构成i便士的种类数
//        int[] dp = new int[N + 1];
//        dp[0] = 1;
//        for (int i = 0, len = nums.length; i < len; ++i) {
//            for (int j = nums[i]; j <= N; ++j) {
//                dp[j] += dp[j - nums[i]];
//            }
//        }
//        System.out.println(dp[N]);
//    }



    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
